package 牛客算法篇;

import java.util.ArrayList;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-06
 * Time:16:55
 */

/**
 *
 牛客算法篇:BM45 滑动窗口的最大值
 描述
 给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。
 例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
 窗口大于数组长度或窗口长度为0的时候，返回空。
 数据范围： 1≤n≤100001≤n≤10000，0≤size≤100000≤size≤10000，数组中每个元素的值满足 ∣val∣≤10000∣val∣≤10000
 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 示例1
 输入：
 [2,3,4,2,6,2,5,1],3
 返回值：
 [4,4,6,6,6,5]
 */
public class maxInWindows {
    public static void main(String[] args) {
        maxInWindows(new int[]{2,3,4,2,6,2,5,1},3);
    }
    public static ArrayList<Integer> maxInWindows(int[] num, int size) {
        // write code here
//       暴力法:
//        ArrayList<Integer> list = new ArrayList<Integer>();
//        int i = 0;
//        int len = num.length;
//
//        while(i + size < len){
//            int max = Integer.MIN_VALUE;
//            for(int j = i;j < i + size && j < len;j++){
//                max = Math.max(num[j],max);
//            }
//            list.add(max);
//            i++;
//        }
//        return list;
        ArrayList<Integer> list = new ArrayList<Integer>();
        int len = num.length;
        if(size == 0 || size > len){
            return list;
        }
        int curindex = 0;
        int maxindex = 0;

        while(curindex < size){
            if(num[curindex] > num[maxindex]){
                maxindex = curindex;
            }
            curindex++;
        }
        list.add(num[maxindex]);
        while(curindex < len){
            if(num[curindex] > num[maxindex]){
                maxindex = curindex;
            }else if(curindex - maxindex == size){
                int  tmpindex = maxindex + 1;
                maxindex = tmpindex;
                while(tmpindex <= curindex){
                    if(num[tmpindex] > num[maxindex]){
                        maxindex = tmpindex;
                    }
                    tmpindex++;
                }
            }
            curindex++;
            list.add(num[maxindex]);
        }


        return list;
    }
}
